package entity;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * 无向图
 *
 * @Author: wanqian
 * @Date: 2021/2/24 0:11
 */
public class Graph {
    public static void main(String[] args) {
        String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
        int n = Vertexs.length; // 结点的个数
        Graph graph = new Graph(n);
        for (String vertex : Vertexs) {
            graph.insertVertex(vertex);
        }
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        graph.insertEdge(3, 7, 1);
        graph.insertEdge(4, 7, 1);
        graph.insertEdge(2, 5, 1);
        graph.insertEdge(2, 6, 1);
        graph.insertEdge(5, 6, 1);
        //显示一把邻结矩阵
        graph.showGraph();

        //测试一把，我们的dfs遍历是否ok
        System.out.println("深度遍历");
        graph.dfs(); // [1->2->4->8->5->3->6->7]
        System.out.println();
        System.out.println("广度优先!");
        graph.bfs(); // [1->2->3->4->5->6->7->8]
    }

    private ArrayList<String> vertexList;

    private int[][] edges;

    private int numOfEdges;

    public Graph(int num) {
        edges = new int[num][num];
        vertexList = new ArrayList<>(num);
        numOfEdges = 0;
    }

    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    public int getNumOfEdges() {
        return numOfEdges;
    }

    public int getNumOfVertex() {
        return vertexList.size();
    }

    public String getValueByIndex(int index) {
        return vertexList.get(index);
    }

    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    public void showGraph() {
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    /**
     * 获取第一个相邻顶点
     *
     * @param index
     * @return
     */
    public int getFirstNeighbor(int index) {
        //因为是双向图，前面顶点进行遍历时已经遍历过了，所有没必要走回头路
        for (int i = index + 1; i < vertexList.size(); i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 获取front顶点出发，current之后的相邻节点
     *
     * @param front
     * @param current
     * @return
     */
    public int getNextNeighbor(int front, int current) {
        for (int i = current + 1; i < vertexList.size(); i++) {
            if (edges[front][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 广度优先遍历
     *
     * @param isVisited
     * @param i
     */
    private void bfs(boolean[] isVisited, int i) {
        int u;
        int w;
        //记录节点访问顺序
        LinkedList<Integer> queue = new LinkedList<>();
        isVisited[i] = true;
        System.out.println(vertexList.get(i));
        queue.addLast(i);
        while (!queue.isEmpty()) {
            //从已访问队列中取出头节点进行广度优先遍历
            u = queue.removeFirst();
            w = getFirstNeighbor(u);
            while (w != -1) {
                if (!isVisited[w]) {
                    System.out.println(vertexList.get(w));
                    isVisited[w] = true;
                    queue.addLast(w);
                }
                w = getNextNeighbor(u, w);
            }
        }

    }

    public void bfs() {
        boolean[] isVisited = new boolean[vertexList.size()];
        //此for循环实际上非必要，除非是两个分开的图
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }

    /**
     * 深度优先遍历
     *
     * @param isVisited
     * @param i
     */
    private void dfs(boolean[] isVisited, int i) {
        isVisited[i] = true;
        System.out.println(vertexList.get(i));
        //最近的一个相邻顶点
        int w = getFirstNeighbor(i);
        while (w != -1) {
            if (!isVisited[w]) {
                dfs(isVisited, w);
            }
            //下一个相邻顶点，若遍历完仍没有则返回-1
            w = getNextNeighbor(i, w);
        }
    }

    public void dfs() {
        boolean[] isVisited = new boolean[vertexList.size()];
        //此for循环实际上非必要，除非是两个分开的图
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                dfs(isVisited, i);
            }
        }
    }
}
